package com.dh.leetcode.six;

import org.junit.Assert;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;


/**
 * @ClassName: _697_degree_of_an_array
 * @Description: 697. 数组的度
 * 给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。
 * <p>
 * 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。
 * <p>
 * <p>
 * <p>
 * 示例 1：
 * <p>
 * 输入：[1, 2, 2, 3, 1]
 * 输出：2
 * 解释：
 * 输入数组的度是2，因为元素1和2的出现频数最大，均为2.
 * 连续子数组里面拥有相同度的有如下所示:
 * [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
 * 最短连续子数组[2, 2]的长度为2，所以返回2.
 * 示例 2：
 * <p>
 * 输入：[1,2,2,3,1,4,2]
 * 输出：6
 * <p>
 * <p>
 * 提示：
 * <p>
 * nums.length 在1到 50,000 区间范围内。
 * nums[i] 是一个在 0 到 49,999 范围内的整数。
 * <p>
 * https://leetcode-cn.com/problems/degree-of-an-array/
 * @Author: shouzimu
 * @Date: 2021/2/20 11:10
 */
public class _697_degree_of_an_array {
    /**
     * 度：出现次数最多的元素个数
     *
     * 第一次遍历，找出每个元素出现的次数和起始位置
     *
     * 第二次遍历，找出最大的度
     *
     * 第三次遍历，找出度数等于最大度的数字，比较起始位置找出最小的
     * @param nums
     * @return
     */
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Mark> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            Mark m = map.getOrDefault(num, new Mark());
            if (m.getStart() == -1) {
                m.setStart(i);
            }
            m.setEnd(i);
            m.setCount(m.getCount() + 1);
            map.put(num, m);
        }

        int du = 0;
        for (Map.Entry<Integer, Mark> integerIntegerEntry : map.entrySet()) {
            du = Math.max(du, integerIntegerEntry.getValue().getCount());
        }
        int min = Integer.MAX_VALUE;
        for (Map.Entry<Integer, Mark> integerIntegerEntry : map.entrySet()) {
            Mark m = integerIntegerEntry.getValue();
            if (m.getCount() == du) {
                min = Math.min(m.getEnd() - m.getStart() + 1, min);
            }
        }
        return min;
    }

    static class Mark {
        private int count;
        private int start;
        private int end;

        public int getCount() {
            return count;
        }

        public void setCount(int count) {
            this.count = count;
        }

        public int getStart() {
            return start;
        }

        public void setStart(int start) {
            this.start = start;
        }

        public int getEnd() {
            return end;
        }

        public void setEnd(int end) {
            this.end = end;
        }

        public Mark() {
            this.start = -1;
        }
    }

    @Test
    public void findShortestSubArrayTest() {
        Assert.assertEquals(2, findShortestSubArray(new int[]{1, 2, 2, 3, 1}));
        Assert.assertEquals(6, findShortestSubArray(new int[]{1, 2, 2, 3, 1, 4, 2}));
    }
}
